1. Field of the Invention
The embodiments described herein are related to methods for Low-Density Parity-Check decoding and more particularly to methods for achieving reduced complexity Low-Density Parity-Check decoders.
2. Background of the Invention
A Low-Density Parity-Check (LDPC) code is an error correcting code that provides a method for transferring a message over a noisy transmission channel. While LDPC techniques cannot guaranty perfect transmission, the probability of lost information can be made very small. In fact, LDPC codes were the first to allow data transmission rates at close to the theoretical maximum, e.g., the Shannon Limit. LDPC techniques use a sparse parity-check matrix, e.g, a matrix populated mostly with zeros, hence the term low-density. The sparse matrix is randomly generated subject to the defined sparsity constraint.
LDPC codes can be defined as both a matrix and a graphical form. An LDPC matrix will have a certain number of rows (M) and columns (N). The matrix can also be defined by the number of 1's in each row (wr) and the number of 1's in each column (wc). For a matrix to be considered low-density the following conditions should be met: wc<<N and wr<<M. An LDPC matrix can be regular or irregular. A regular LDPC matrix, is one in which wc is constant for every column and wr=wc*(M/N) is also constant for every row. If the matrix is low-density but the number of 1's in each row or column is not constant, then such codes are called irregular LDPC code.
It will also be understood that an LDPC code can be graphically defined by its corresponding Tanner graph. Not only do such graphs provide a complete representation of the code, they also help to describe the decoding algorithm as explained in more detail below. A Tanner graph comprises nodes and edges. The nodes are separated into two distinctive sets, or types, and the edges connect the two different types of nodes. The two types of nodes in a Tanner graph are called the variable nodes (v-nodes) and check nodes (c-nodes), or parity nodes. Thus, the Tanner graph will consist of M check nodes (the number of parity bits) and N variable nodes (the number of bits in a code word). A check node will then be connected to a variable node if there is a 1 in the corresponding element of the LDPC matrix.
The number of information bits can be represented as (K). A Generator Matrix (GK×N) can then be defined according to the following:
cN×1=GN×K dK×1, where                dK×1=a message or data word, and        cN×1=a code word.        
As can be seen, the code word cN×1 is generated by multiplying the message by the generator matrix. The subscripts are matrix notation and refer to the number of rows and columns respectfully. Thus, the data word and code word can be represented as single column matrices with K and N rows respectfully.
The parity check Matrix can be defined as HM×NcN×1=0.
Accordingly, FIG. 1 is a diagram illustrating a system 100 that includes a transmitter and a receiver. A portion 102 of the transmitter and a portion 110 of the receiver are shown for simplicity. Referring to FIG. 1, an encoder 104 converts a data word dK×1 into a code word cN×1 via application of the generator matrix GK×N. Modulator 106 can be configured to then modulate code word cN×1 onto a carrier so that the code word can be wirelessly transmitted across channel 108 to the receiver.
In receive portion 110, demodulator 112 can be configured to remove the carrier from the received signal; however, channel 108 will add channel effects and noise, such the signal produced by demodulator 112 can have the form: rN×1=2/σ2(1−2 cN×1)+wN×1, where r is a multilevel signal. As a result of the noise and channel effects, some of data bits d will be lost in the transmission. In order to recover as much of the data as possible, decoder 114 can be configured to use the parity check matrix HM×N to produce an estimate d′K×1 of the data that is very close to the original data dK×1. It will be understood that decoder 114 can be a hard decision decoder or a soft decision decoder. Soft decision decoders are more accurate, but also typically require more resources.
In order to illustrate the operation of LDPC codes, the following example is presented:
      H          3      ×      6        =      [                            1                          0                          1                          0                          1                          0                                      0                          1                          0                          1                          0                          1                                      1                          1                          0                          0                          0                          1                      ]  
As can be seen, the example parity check matrix H is low density, or sparse. The first row of matrix H defines the first parity check node, or equation. As can be seen, the first parity check node will check received samples r0, r2, and r4, remembering that r is the multilevel signal produced by demodulator 112 in the receiver. The second parity check node, i.e., the second row of H, checks for received samples r1, r3, and r5, and the third parity check node checks samples r0, r1, and r5. In this example, there are three parity check nodes and six samples. The first and second parity check nodes are considered orthogonal, because they involve mutually exclusive sets of samples.
If it is assumed that K=3 and M=3, then the following is true:
            H              3        ×        6              ⁢          c              6        ×        1              =            0      ⁢            ⁢                        H                      3            ×            6                          ⁡                  [                                                                      d                                      3                    ×                    1                                                                                                                        p                                      3                    ×                    1                                                                                ]                      =                  0        ⁢                                          ⁡                          [                                                                    1                                                        0                                                        1                                                        0                                                        1                                                        0                                                                                        0                                                        1                                                        0                                                        1                                                        0                                                        1                                                                                        1                                                        1                                                        0                                                        0                                                        0                                                        1                                                              ]                                ⁡                      [                                                                                d                    0                                                                                                                    d                    1                                                                                                                    d                    2                                                                                                                    p                    0                                                                                                                    p                    1                                                                                                                    p                    2                                                                        ]                              =      0      
This produces the following equations:d0+d2+p1=0d1+p0+p2=0d0+d1+p2=0
These equations reduce to:p0=d0 p1=d0+d2 p2=d0+d1 
Thus, for example, if d=[0;1;0], then p=[0;0;1] and c=[0;1;0;0;0;1].
FIG. 2 is a Tanner Graph illustrating the operation of H in the example above. As can be seen, the graph of FIG. 2 has three parity check nodes 202, 204, and 206, and 6 variable nodes 208, 210, 212, 214, 216, and 218, which correspond to the bits of c. Parity check nodes 202, 204, and 206 are connected with variable nodes 208, 210, 212, 214, 216, and 218, via edges 220, 222, 224, 226, 228, 230, 232, 234, and 236 as dictated by the entries in H. In other words, each edge 220, 222, 224, 226, 228, 230, 232, 234, and 236 should correspond to a 1 in H.
In an LDPC decoder, the operations of the parity check and variable nodes can be implemented by processors. In other words, each parity check node can be implemented by a parity check processor, and each variable check node can be implemented by a variable node processor. An LDPC decoder is then an iterative decoder that implements a message passing algorithm defined by H.
Unfortunately, conventional LDPC decoding techniques result in a high complexity, fully parallel decoder implementations where all the messages to and from all the parity node processors have to be computed at every iteration in the decoding process. This leads to large complexity, increased resource requirements, and increased cost.
Hence, there are many current efforts devoted to reducing the complexity of check node message updating, while keeping the performance loss as small as possible. The most common simplification is the min-sum algorithm (MSA), which has greatly reduced the complexity of check node updates, but incurs a 0.3-0.4 dB degradation in performance relative to standard sum-product algorithm (SPA) check node implementations. To combat this performance degradation, modifications of the MSA using a normalization term and an offset adjustment term have also been proposed. Such solutions do have reduced performance loss compared with the more conventional MSA implementations, but there is still significant performance loss. In addition, two-dimensional MSA schemes have been proposed that can further improve the performance of MSA with some additional complexity. Thus, in conventional implementations, there is a constant trade-off between complexity and performance.